package base.Chapter00_Structures.C01_Array;

/**
 * 功能说明：
 * 求中位数可以分为两种情况
 * 1、数据个数为奇数时（即为单数时）: 中间的数
 * 2、数据个数为偶数时（即为双数时）: 中间两个数的平均值
 * <p>
 * <p>
 * 算法的时间复杂度应该为 O(log (m+n))  --> 二分法
 * 开发人员：@author MaLi
 */
public class L04_寻找两个正序数组的中位数 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //1, 合并数组: 按序合并
        //1.1 非空验证: 同时为空, 返回0
        if (nums1 == null && nums2 == null || nums1.length == 0 && nums2.length == 0) {
            return 0;
        }
        //1.2 申请一个新数组长度为两者之和lengthsum
        int length = nums1.length + nums2.length;
        double[] nums = new double[length];
        int point1 = 0, point2 = 0;
        for (int i = 0; i < length; i++) {
            if (point1 < nums1.length && point2 < nums2.length) {
                nums[i] = nums1[point1] <= nums2[point2] ? nums1[point1++] : nums2[point2++];
            } else if (point1 == nums1.length) {
                nums[i] = nums2[point2++];
            } else if (point2 == nums2.length) {
                nums[i] = nums1[point1++];
            }
        }
        //2, 分两种情况:
        if (length % 2 == 1) {
            //2.1 奇数
            return nums[length / 2];
        } else {
            //2.2 偶数, 找中间两个数   [1,2,3,4]
            return (nums[length / 2 - 1] + nums[length / 2]) / 2;
        }
    }
}
